Go 使用 goyacc 实现四则运算解析

GoYACC 是 Golang 版本的 YACC，本篇博文参考官网的例子

其实语法解析就是根据 token 去拼出多个解析规则，然后通过递归下降等算法去解析。而 yacc 就是是通过 .y 描述文件生成递归下降程序（y.go程序）实现语法解析的一个过程。

首先安装：

go get -u golang.org/x/tools/cmd/goyacc

参数	说明
-l	显示line指令
-o string	指定输出解析器的文件名称（默认 y.go）
-p string	指定解析器输出接口的前缀
-v string	生成解析过程表（默认 y.output）

goyacc 会生成一个语义解析代码，其中它内部有两个重要的 interface, 其中 yyLexer 需要使用者自己实现提供，yacc 会生成 yyParser 的实现，其使用 yyLexer 做解释操作。解释的过程和解释前后都可以嵌入自己的代码逻辑，完成一个程序或者单纯生成一个自定义的语法树结构.

YACC 文件的写法

首先来看一下这个 yacc 文件（以 .y 后缀）的语法

{%
  嵌入代码: go 代码
%}

文法定义: 由 %union %type %token %left %right %start 等组成的定义

%%
文法规则: 由 非终结符 与 终结符 组成的匹配 + 动作规则
%%

嵌入代码 （这部分为可选，比如可以 lexer 或者 main 可以写在这里或者单独用文件写 ）

名称	解释
嵌入代码	golang代码通常用来定义生成的文件的包名、引入包、结构定义等
文法定义	由 %union %type %token %left %right %start 等组成的定义
文法规则	由非终结符与终结符组成的规则

文法定义

简单说明如下：

描述符	说明
%union	用来定义一个类型并映射 golang 的一个数据类型
%struct	同 %union 建议使用 %union
%token	定义终结符，表示不能再拆了的字符是一个 union 中定义的类型
%type	定义非终结符
%start	定义从哪个终结符开始解析默认规则段中的第一个终结符
%left	定义规则结合性质左优先
%right	定义规则结合性质右优先
%nonasso	定义规则结合性质不结合
%perc term	定义优先级与 term 一致

定义一个 val 类型映射到 golang 的string类型, 定义一个stu 映射到 golang 中定义的一个 Student 结构体类型

%union {
    val string
    stu Student
}

文法规则

非终结符: 规则描述 {
动作描述
};

这个 “:” 左边的是非终结符右侧的规则通常由非终结符终结符构成

非终结符：使用 %type 定义的符号可以理解为一串特定排序的 token

终结符：可以理解成一个 token

规则描述：可以是非终结符、终结符，可用 | 分割多个规则，{} 内是具体动作，{} 内符合 Go 语法，并且 $$ 代表规约后的值， $1、$2 代表类型变量值动作描述

如下：这个 $$ 表示 expr1，$1 表示第一个 NUM，$3 代表第二个 NUM

expr1: NUM '+' NUM {
 $$ = $1 + $3
};

用 “{” 与 “}” 包裹的部分符合 Go 语法且拥有特殊宏替换的语法块，一条规则最后要用 “;” 结束

例子1:

expr1: NUM '+' NUM {
 $$ = $1 + $3
};

这个例子定义了一个两数求和的规则（a+b）

expr 构成终结符这个非终结符的条件有三个终结符（token）构成 NUM '+' NUM ，方法是求两数之和并返回给 expr1

例子2:

当需要定一个多个数求和时就需要通过递归定义了

expr2: expr1 '+' NUM {
 $$ = $1 + $3
};

这个例子表示三个数求和，并使用了一个非终结符作为规则的一部分

例子3:

expr3: expr3 '+' NUM {
   $$ = $1 + $3
} | NUM '+' NUM {
  $$ = $1 + $3
};

这个例子通过递归定义了支持多个数相加的规则其中使用 “｜” 分割了两个规则描述

实现 lexer 接口

goyacc 没有对应的 lex 生成工具通常需要手工写两个方法来实现 yyLexer 接口

type yyLexer interface {
    Lex(lval *yySymType) int
    Error(s string)
}

介绍这两个函数：

Lex() 词法分析函数解析过程会多次回调此方法，每次调用应返一个token值，lval 是当前栈状态值
Error() 错误回调方法在语法解析错误时被回调

一般可以通过 text/scanner 进行基础解析，再换算成自己的token，省去部分烦劳工作

简单的 Hello World

以下创建一个最简单的 HelloWorld 为例，文件名为 hello.y：

%{
package main
import "fmt"
%}
 
%union {
    type_string string
}
 
%type <type_string> expression
 
%token <type_string> PRINT HELLO
 
%%
expression: HELLO
{
    fmt.Println("Hello World!")
}
%%

生成文件

goyacc -o hello.go -p hello hello.y

这句代码表示使用的 y 源文件为 hello.y，生成的目标 Parser 代码为 hello.go

上面说过，Lexer 可以写在另外一个文件里面，这里实习 helloLexer 接口

type helloLexer interface {
  // 对输入的一行命令执行逐字符扫描，返回匹配到的 Token
    Lex(lval *helloSymType) int
  // 输入的文本无法在文件中找到对应的 Token 的时候应该做啥
    Error(s string)
}

在 lexer.go 文件里面实现这个接口

package main
 
import (
    "fmt"
    "time"
)
 
type myLexer struct {
    //待解析指令暂时存input里面，用byte数组方便逐字符操作
    input []byte
    //当前扫描到字符的索引
    index int
    //存储已经扫描到的内容，当内容为hello时，返回HELLO
    buffer string
}
 
func (m *myLexer) Lex(lval *helloSymType) int {
    if len(m.input) == 0 {
        return 0 //表示已经解析完所有的内容了
    }
    for i := 0; i < len(m.input); i++ {
        char := m.input[i]
        switch char {
        case 'h', 'e', 'l', 'o':
            m.buffer += string(char)
        }
        if m.buffer == "hello" {
            return HELLO
        }
    }
    return 0
}
 
func (m *myLexer) Error(s string) {
    fmt.Println(s)
}
 
func main() {
    //正确使用
    helloParse(&myLexer{
        input:  []byte("hello"),
        index:  0,
        buffer: "",
    })
    time.Sleep(time.Second)
    //未定义语法，会报错
    helloParse(&myLexer{
        input:  []byte("hhhhhh"),
        index:  0,
        buffer: "",
    })
}

输出：

Hello World!
syntax error

自定义四则运算

词法分析模块：词法分析模块主要将输入的表达式转化为一个个的 token 转交语法分析模块处理。

比如表达式 “1” 这个被词法分析解析成一个 “NUMBER” 类型，并将该类型的值 1 存储在 l.val.num 中，这个变量定义在语法分析模块中的 %union 域中。

%union {
    num float64
}

%type <num> expression term factor
%token '+' '-' '*' '/' '(' ')'
%token <num> NUMBER

语法分析模块：这个模块本质就是按照 yacc 的语法定义文法，goyacc 会将该文件转化为一个分析引擎。

可以在 VsCode 下载一个语法高亮插件

完整的 calcyacc.y 文件

%{
package main
%}

%union {
    num float64
}

%type <num> expression term factor
%token '+' '-' '*' '/' '(' ')'
%token <num> NUMBER

%%
top        : expression
                { 
                    if l, ok := yylex.(*simpleLex); ok {
                        l.value = $1
                    }
                }
           ;
expression : expression '+' term
                { $$ = $1 + $3 }
           | expression '-' term
                { $$ = $1 - $3 }
           | term
                { $$ = $1 }
           ;
term       : term '*' factor
                { $$ = $1 * $3 }
           | term '/' factor
                { $$ = $1 / $3 }
           | factor
                { $$ = $1 }
           ;
factor     : NUMBER
                { $$ = $1 }
           | '(' expression ')'
                { $$ = $2 }
           ;
%%

然后实现生成的接口：

type yyLexer interface {
    Lex(lval *yySymType) int
    Error(s string)
}

package main

import (
    "log"
    "strconv"
    "strings"
    "text/scanner"
)

var LexPrintToken = false

type Token struct {
    Type int
    Str  string
}

type simpleLex struct {
    scanner.Scanner
    value float64
}

// 这个接口必须实现，是词法分析的入口
func (s *simpleLex) Lex(lval *yySymType) int {
    r, lit := s.Scan(), s.TokenText()
    var token Token
    token.Str = lit

    switch r {
    case scanner.EOF:
        return 0
    case scanner.Int:
        i, _ := strconv.Atoi(lit)
        lval.num = float64(i)
        token.Type = scanner.Float
    case scanner.Float:
        lval.num, _ = strconv.ParseFloat(lit, 64)
        token.Type = scanner.Float
    default:
        token.Type = int(r)
    }

    if token.Type == scanner.Float {
        return NUMBER
    } else {
        return token.Type
    }
}

// 词法分析异常处理 该接口必须实现
func (s *simpleLex) Error(s1 string) {
    log.Printf("parse error: %s", s1)
}

// 计算入口
func Parse(code string) float64 {
    s := new(simpleLex)
    s.Init(strings.NewReader(code))
    yyParse(s)
    return s.value
}

编写单元测试

package main

import (
    "testing"
)

func TestParse(t *testing.T) {
    tests := []struct {
        code  string
        value float64
    }{
        {"1", 1},
        {"1+1", 2},
        {"1+2*3", 7},
        {"1+3/1", 4},
        {"1-1", 0},
        {"(1+2)*3", 9},
        {"(1+2)/3", 1},
        {"1+(2*3)", 7},
        {"3*2+1", 7},
        {"3*(2+1)", 9},
        {"1*2*3", 6},
        {"1+2+3", 6},
        {"1/2", 0.5},
        {"2/3", 0.6666666666666666},
    }

    for _, test := range tests {

        if value := Parse(test.code); value != test.value {
            t.Errorf("err Actual: %.16f Expect: %f", value, test.value)
        } else {
            t.Logf(" sucess %s = %f", test.code, test.value)
        }
    }
}

使用这个单元测试：

goyacc -o calcyacc.go calcyacc.y && go test -v

output

=== RUN   TestParse
    calcLex_test.go:33:  sucess 1 = 1.000000
    calcLex_test.go:33:  sucess 1+1 = 2.000000
    calcLex_test.go:33:  sucess 1+2*3 = 7.000000
    calcLex_test.go:33:  sucess 1+3/1 = 4.000000
    calcLex_test.go:33:  sucess 1-1 = 0.000000
    calcLex_test.go:33:  sucess (1+2)*3 = 9.000000
    calcLex_test.go:33:  sucess (1+2)/3 = 1.000000
    calcLex_test.go:33:  sucess 1+(2*3) = 7.000000
    calcLex_test.go:33:  sucess 3*2+1 = 7.000000
    calcLex_test.go:33:  sucess 3*(2+1) = 9.000000
    calcLex_test.go:33:  sucess 1*2*3 = 6.000000
    calcLex_test.go:33:  sucess 1+2+3 = 6.000000
    calcLex_test.go:33:  sucess 1/2 = 0.500000
    calcLex_test.go:33:  sucess 2/3 = 0.666667
--- PASS: TestParse (0.00s)
PASS
ok      stgo    0.243s

YACC 文件的写法​

文法定义​

文法规则​

实现 lexer 接口​

简单的 Hello World​

自定义四则运算​

References​